#子问题的重复计算
def fibnacci(n):#递归法
    if n==1 or n==2:
        return 1
    else:
        return fibnacci(n-1)+fibnacci(n-2)
#动态规划(DP)的思想=递推式+重复的子问题
def fibancci_no_recurision(n):#非递归法
    f=[0,1,1]
    if n>2:
        for i in range(n-2):
            num=f[-1]+f[-2]#f的最后一项和倒数第二项
            f.append(num)
    return f[-1]
print(fibnacci(5))
